# -*- coding: utf-8 -*--

import exceptions,math, collections, sys
import carte, courbe


class ErreurFigurine( exceptions.Exception ):
    pass


MOUVEMENT_INFINI = -1
CASE_PORTE = "X"
NON_VISITE, VISITE = "0", "1"

class Figurine:

    def __init__( self, o_carte, i_position_x, i_position_y ):
        if not isinstance( o_carte, carte.Carte ):
            raise ErreurFigurine( "Le premier paramtre du constructeur doit être un objet de la classe Carte" )            
        self.__o_carte = o_carte
        self.__verifPosition( i_position_x, i_position_y )
        self.__i_position_x = i_position_x
        self.__i_position_y = i_position_y
        self.__o_carte.addFigurine( self )
        self.__i_mouvement_max = MOUVEMENT_INFINI 
        self.__i_mouvement_restant = 0    
    
    def getPosition( self ):
        return ( self.__i_position_x, self.__i_position_y )
        
    def getMouvementMax( self ):
        return self.__i_mouvement_max
    
    def setMouvementMax( self, i_mouvement_max ):
        self.__i_mouvement_max =  i_mouvement_max
        
    def getMouvementRestant( self ):
        return self.__i_mouvement_restant
    
    def setMouvementRestant( self, i_mouvement_restant ):
        self.__i_mouvement_restant =  i_mouvement_restant
        
    def move( self, i_position_x, i_position_y ):
        self.__verifPosition( i_position_x, i_position_y )
        for fig in self.__o_carte.getFigurines( ):
            if fig != self:
                if fig.getPosition( ) == self.getPosition( ):
                    raise carte.ErreurCarte( "Une figurine se trouve deja sur cette case" )
        if( self.__o_carte.hasMur( i_position_x, i_position_y ) ):
            raise carte.ErreurCarte( "Un mur se trouve sur cette case" )
        self.__i_position_x = i_position_x
        self.__i_position_y = i_position_y
    
    def makeShortWay( self, i_position_x, i_position_y ):
        self.__verifPosition( i_position_x, i_position_y ) 
        
        l_chemin = list( )
        l_pile   = collections.deque( )
        
        l_non_visite = list( list( NON_VISITE * self.__o_carte.getLargeur( ) ) * self.__o_carte.getHauteur( ) )                
        depart  = { "X":self.__i_position_x, "Y":self.__i_position_y, "cout":(self.__o_carte.getLargeur()*self.__o_carte.getHauteur()*10), "rang":0 }
        arrivee = { "X":i_position_x, "Y":i_position_y, "cout":0, "rang":0 }
        l_pile.append( depart )
        l_poper = list( )
        while( len( l_pile ) != 0 ):
            point_courant = l_pile[0]
            rang_courant = point_courant["rang"] + 1
            i = 0
            while i < len( l_pile ):
                point = l_pile[i]
                try:
                    self.__verifPosition( point["X"], point["Y"] )
                except( ErreurFigurine ):
                    pass
                else:
                    if( point_courant["cout"] > point["cout"] and point_courant["rang"] == point["rang"] ):
                        point_courant = point
                             
                i += 1
            index = 0
            for element in l_pile:
                if element == point_courant:
                    del l_pile[index]
                    break
                index += 1
                            
            l_chemin.append( point_courant )
            l_non_visite[ self.__o_carte.getPgcd( point_courant["X"], point_courant["Y"] ) ] = VISITE
                    
            if( point_courant["X"] == arrivee["X"] and point_courant["Y"] == arrivee["Y"] ):
                l_chemin.reverse( )
                i_rang_precedent = 100000000000000000
                l_resultat = list( )
                for element in l_chemin:
                    if element["rang"] < i_rang_precedent:
                        l_resultat.append( element )
                        i_rang_precedent = element["rang"]
                l_resultat.reverse( )  
                del l_resultat[0]
                return l_resultat
            else:
                i_compteur = 0              

                # OUEST
                x, y = point_courant["X"] - 1, point_courant["Y"]
                try:
                    self.__verifPosition( x, y )
                except( ErreurFigurine ):
                    pass
                else:
                    if l_non_visite[ self.__o_carte.getPgcd( x, y ) ] == NON_VISITE and not self.__o_carte.hasElement( x, y ):
                        point = { "X":x, "Y":y, "cout":self.getCout( x, y, arrivee["X"], arrivee["Y"] ), "rang":rang_courant }
                        l_pile.appendleft( point )
                        i_compteur += 1
                        l_non_visite[ self.__o_carte.getPgcd( x, y ) ] = VISITE
                
                # EST
                x, y = point_courant["X"] + 1, point_courant["Y"]
                try:
                    self.__verifPosition( x, y )
                except( ErreurFigurine ):
                    pass
                else:
                    if l_non_visite[ self.__o_carte.getPgcd( x, y ) ] == NON_VISITE and not self.__o_carte.hasElement( x, y ):
                        point = { "X":x, "Y":y, "cout":self.getCout( x, y, arrivee["X"], arrivee["Y"] ), "rang":rang_courant }
                        l_pile.appendleft( point )
                        i_compteur += 1
                        l_non_visite[ self.__o_carte.getPgcd( x, y ) ] = VISITE
                        
                # NORD
                x, y = point_courant["X"], point_courant["Y"] - 1
                try:
                    self.__verifPosition( x, y )
                except( ErreurFigurine ):
                    pass
                else:
                    if l_non_visite[ self.__o_carte.getPgcd( x, y ) ] == NON_VISITE and not self.__o_carte.hasElement( x, y ):
                        point = { "X":x, "Y":y, "cout":self.getCout( x, y, arrivee["X"], arrivee["Y"] ), "rang":rang_courant }
                        l_pile.appendleft( point )
                        i_compteur += 1
                        l_non_visite[ self.__o_carte.getPgcd( x, y ) ] = VISITE  
                          
                # SUD
                x, y = point_courant["X"], point_courant["Y"] + 1
                try:
                    self.__verifPosition( x, y )
                except( ErreurFigurine ):
                    pass
                else:
                    if l_non_visite[ self.__o_carte.getPgcd( x, y ) ] == NON_VISITE and not self.__o_carte.hasElement( x, y ):
                        point = { "X":x, "Y":y, "cout":self.getCout( x, y, arrivee["X"], arrivee["Y"] ), "rang":rang_courant }
                        l_pile.appendleft( point )
                        i_compteur += 1
                        l_non_visite[ self.__o_carte.getPgcd( x, y ) ] = VISITE    
                if( i_compteur == 0 ):
                    x, y = point_courant["X"], point_courant["Y"]
                    l_non_visite[ self.__o_carte.getPgcd( x, y ) ] = VISITE
                    l_chemin.pop( )
                    l_pile.popleft( )

    
    def getCout(self, i_position_depart_x, i_position_depart_y, i_position_arrive_x, i_position_arrive_y ):        
        i_cout = math.hypot( i_position_arrive_x - i_position_depart_x, i_position_arrive_y - i_position_depart_y )
        return i_cout

    def moveOnWay( self, l_way ):        
        for point in l_way:
            if( self.__i_mouvement_restant == 0 ):
                break
            self.move( point["X"], point["Y"] )
            self.__i_mouvement_restant -= 1
    
    def getCaseVisible( self ):
        l_resultat = list( )
        l_resultat.append( ( self.__i_position_x, self.__i_position_y ) )# la figurine voit la case où elle se trouve
        o_courbe = courbe.Courbe( )
        d_position = { "X":self.__i_position_x, "Y":self.__i_position_y }
        l_perimetre = self.__o_carte.getPerimetre( )
        l_perimetre.sort()
        for point in l_perimetre:
            d_point = { "X":point[0], "Y":point[1] }
            o_courbe.setPoints( d_position, d_point )
            o_courbe.resolve( )
            #print d_position,point,range( d_position["X"], d_point["X"] )
            if( abs( d_position["X"] - d_point["X"] ) > abs( d_position["Y"] - d_point["Y"] ) ):          
                if d_position["X"] >  d_point["X"]:                    
                   l_range = range( d_point["X"], d_position["X"]  )
                   l_range.reverse( )
                else:
                    l_range = range( d_position["X"] + 1, d_point["X"] + 1 )
                print d_point,"X",l_range
                for x in l_range:
                    y = int( round( o_courbe.getY( x ) ) )
                    #print (x,y)
                    if not self.__o_carte.hasElement( x, y):
                        if ( x, y ) not in l_resultat:
                            print "j'ajoute",( x, y )
                            l_resultat.append( ( x, y ) )   
                    else:
                        break
            else:
                if d_position["Y"] >  d_point["Y"]:                    
                   l_range = range( d_point["Y"], d_position["Y"]  )
                   l_range.reverse( )
                else:
                    l_range = range( d_position["Y"] + 1 , d_point["Y"] + 1 )
                print d_point,"Y",l_range
                for y in l_range:
                    x = int( round( o_courbe.getX( y ) ) )
                    if not self.__o_carte.hasElement( x, y):
                        if ( x, y ) not in l_resultat:
                            print "j'ajoute",( x, y )
                            l_resultat.append( ( x, y ) )
                    else:
                        break
        print len( l_resultat )
        return l_resultat
    
    def __verifPosition( self, i_position_x, i_position_y ):
        if i_position_x >= self.__o_carte.getLargeur( ) or i_position_y >= self.__o_carte.getHauteur( ) or i_position_x < 0 or i_position_y < 0:
            raise ErreurFigurine( "La figurine n'a pas une position correcte" )